Some open problems on cycles

分类： 数学 >> 离散数学和组合数学 提交时间： 2024-03-27

Chunhui LAI Mingjing Liu

摘要： Let f(n) be the maximum number of edges in a graph on n vertices in which no two cycles have the same length. Erd¨os raised the problem of determining f(n). Erd¨os conjectured that there exists a positive constant c such that ex(n, C2k) ≥ cn1+1/k. Haj´os conjecture that every simple even graph on n vertices can be decomposed into at most n/2 cycles. We present the problems, conjectures related to these problems and we summarize the know results. We do not think Haj´os conjecture is true.

通过

 点击量 1657  下载量 522  评论